1. Field of the Invention
The present invention relates to a secure parameter generating device, a generating method, and a storing medium in a discrete logarithm cryptography (hereinafter, referred to an algebraic curve cryptography), and more particularly to a secure parameter generating device and its generating method in a discrete logarithm cryptography using Jacobian group of algebraic curve.
2. Description of the Related Art
A discrete logarithm cryptography is a public key system based on the difficulty of a discrete logarithm problem on a given finite field. In order to keep the security of cryptography, the order of the finite field must be almost a prime number, that is, a factor of small integer and large integer. The algebraic curve cryptography that is one of the discrete logarithm cryptography needs to use an algebraic curve such that the order of the Jacobian group is almost a prime number.
In the case of an elliptic curve that is the simplest algebraic curve, an efficient algorithm of calculating the order of the Jacobian group over any elliptic curve is known. The detailed description is shown in, for example, “Counting points on elliptic curves over finite fields”, Journal de Theorie des Nombres, de Bordeaux 7 (1995), 219–254, Institute de Mathematique de Bordeaux, written by Rene Schoof. The elliptic curve such that the order of the Jacobian group is almost a prime factor can be obtained as follows, by using the above algorithm.                1. Generate a random elliptic curve E.        2. Calculate the order n of the Jacobian group of E.        3. If n is almost a prime number, output E; otherwise, return to 1.        
In the case of an algebraic curve other than an elliptic curve, no efficient algorithm of calculating the order of the Jacobian group is known except for one hyper-elliptic curve. Therefore, the algebraic curve which can be used in the algebraic curve cryptography is limited to an elliptic curve or one exceptional hyper elliptic curve.
As for the h-fold operation of the elements in the Jacobian group, “Software Installation of Discrete Logarithm Cryptography Using Cab curve” written by Arita, Yoshikawa, and Miyauchi, pp. 573–578, Security Symposium on Cryptography and Information in 1999, is known.
Further, the technique disclosed in Japanese Patent Publication Laid-Open (Kokai) No. Heisei 6-282226 comprises a step of selecting any prime number, storing an encryption key corresponding to the prime number into the public file device, generating a decoding key list corresponding to the prime number and the encryption key, and storing the decoding key list together with the prime number into a decoder, wherein an encoder obtains a public key of a receiver (decoder) from the public file, to multiply the plaintext on an elliptic curve, its value is sent to the decoder as a cryptogram, and the decoder computes a parameter of the elliptic curve from the cryptogram and selects a decoding key corresponding to the parameter by use of the decoding key list, thereby obtaining the plaintext from the value obtained by multiplying the cryptogram by the elliptic curve, using Chinese residue theorem.
The above mentioned conventional technique limits the usable algebraic curves to an elliptic curve or one of exceptional hyper-elliptic curve. Since the elliptic curve and the hyper-elliptic curve are extremely particular algebraic curve from the viewpoint of the whole algebraic curves and this narrows the target for cryptanalysis, there arises a security problem of an algebraic curve cryptography.